//
//  BinaryTree.swift
//  ArithmeticWithSwift
//
//  Created by 神州锐达 on 2018/9/26.
//  Copyright © 2018年 onePiece. All rights reserved.
//

import Foundation


//二叉树
//二叉树中,每个节点最多有两个子节点,一般称为左子节点和右子节点,并且节点的顺序不能任意颠倒.第一层的节点称之为根节点,我们从根节点开始计算,到节点的最大层次为二叉树的深度.

//public:不同于OC的public swift中不能在override和继承的extension中访问
//节点
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int){
        self.val = val
    }
}


class Tree {
    //如何求二叉树的深度
    /*
     注解:
     
     1:首先判断入参二叉树节点是否为nil,若不存在的话返回0,若存在递归子节点取最大值.
     
     2:二叉树的深度是从根节点开始计算,这也是为什么在最后我们需要对取到的max值做+1操作.
     */
    func treeMaxDepth(root: TreeNode?) -> Int {
        
        guard let root = root else {
            return 0;//root不存在返回0
        }
        //max函数:比较两个入参的大小取最大值
        return max(treeMaxDepth(root:root.left), treeMaxDepth(root: root.right)) + 1
    }
    
    //二叉查找树
    //在二叉树中有类特别的二叉树叫做二叉查找树(Binary Sort Tree),满足所有左子节点的值都小于它的根节点的值,所有右字节点都大于它的根子节点的值
    
    func isValidBST(root: TreeNode?) -> Bool {
        return _help(node: root, nil, nil)
    }
    
    func _help(node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
        //node不存在 则到了最底层 递归结束.这个要注意的是第一次传入的node不能为nil
        guard let node = node else { return true }
        //右子树的值都必须大于它的根节点的值
        if let min = min, node.val <= min {
            return false
        }
        //左子树的值都必须小于它的根节点的值
        if let max = max, node.val >= max {
            return false
        }
        //左右子树同时递归
        return _help(node: node.left, min, node.val) && _help(node: node.right, node.val, max)
    }
    /*
     注解:
     
     1:这个地方会首先判断当前节点是否存在,若不存在即代表已经递归到最后一层,返回true.
     
     2:然后判断右子树和左子树的val是否满足判断条件,若都满足条件进行下一层的递归.
     
     3:左右同时进行递归操作.
     */
    
    
    /*
     常见的二叉树遍历有前序、中序、后序和层级遍历(广度优先遍历).
     给出几种遍历方法的规则:
     前序遍历规则:
     1:访问根节点
     2:前序遍历左子树
     3:前序遍历右子树
     中序遍历规则:
     1:中序遍历左子树
     2:访问根节点
     3:中序遍历右子树
     后序遍历规则：
     1:后序遍历左子树
     2:后序遍历右子树
     3:访问根节点
     **层级遍历规则:**以层为顺序,将某一层上的节点全部遍历完成后,才向下一层进行遍历,依次类推,至到最后一层.
     */
    
    //广度优先遍历
    func levelOrder(root: TreeNode?) -> [[Int]] {
        //    初始化 遍历后返回的res数组
        var res = [[Int]]()
        //    队列数组
        var queue = [TreeNode]()
        
        if let root = root {
            //        存储入参root节点
            queue.append(root)
        }
        
        while queue.count > 0 {
            //        获取层级个数
            let size = queue.count
            //        每一层 数据存储数组
            var level = [Int]()
            
            for _ in 0..<size{
                //            删除第一个元素 并返回被删除的元素
                let node = queue.removeFirst()
                //            添加数据
                level.append(node.val)
                //判断是否存在 左右子节点 并添加到队列 顺序从左至右
                if let left = node.left{
                    queue.append(left)
                }
                if let right = node.right{
                    queue.append(right)
                }
                
            }
            
            //        存储level数据数组
            res.append(level)
            
        }
        
        return res
    }
    
    /*
     注解:
     1:首先我们声明数组res,用来存储每一层的val数组,并声明队列数组,方便后面判断.
     2:判断入参root是否存在,若存在存储root节点到queue数组中.
     3:while判断queue是否有数据,若有数据则取到queue的第一个数据,并在queue中删除.然后判断下一层的数据,并再次循环遍历.
     4:最后把节点的val数据保存到level中,添加到res.
     
     */
    
    
    
//    有序数组中，查找某一个特定元素的搜索，它从中间的元素开始搜索，若中间元素是要找的元素，则返回；若中间元素小于要找的元素，则要找的元素一定在大于中间元素的那一部分，所以只需要搜索此部分即可，反正亦然。
//    二分搜索，这是一种复杂度更低O(logn)
    
    func binarySearch(_ nums: [Int], _ target: Int) -> Bool {
        //初始化
        var left = 0, mid = 0, right = nums.count - 1
        //边界条件判断
        while left <= right {
            //求出有序数组下标
            mid = (right - left)/2 + left
            //判断当前中间元素与目标元素关系
            if nums[mid] == target {
                //等于mid
                return true
            } else if nums[mid] < target{
                //在mid右边
                left = mid + 1
            } else {
                //在mid左边
                right = mid - 1
            }
        }
        return false
    }
    

    

}
